package zwp.exercise.intereview.base.sort.QuickSort;

import java.util.Arrays;

/**
 * @Author zwp14
 * @create 2024/6/28 17:54
 * @description 单边循环 - 不稳定
 */
public class QuickSort1 {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};
        //调用递归
        recursion(array, 0, array.length - 1);
    }


    /**
     * @param array 数组
     * @param l     左边界
     * @param h     右边界
     */
    private static void recursion(int[] array, int l, int h) {
        //如果左边界>=有边界结束
        if (l >= h) {
            return;
        }
        //第一次分区排序
        int partition = partition(array, l, h);
        //调用递归
        recursion(array, l, partition - 1);
        recursion(array, partition + 1, h);
    }

    private static int partition(int[] array, int l, int h) {

        //基准点元素值
        int endValue = array[h];
        int sign = l;
        //以基准点元素值为界点,划分为两个集合,左侧为小于endValue的集合,右侧为大于endValue的集合
//          最开始的时候,起始索引和标记索引相同,所以i=l
        for (int i = l; i < h; i++) {
            if (array[i] < endValue) {
                exchanger(array, sign, i);
                sign++;
            }
        }
        exchanger(array, sign, h);
        System.out.println(Arrays.toString(array));
        return sign;
    }

    /**
     * @param array 数组
     * @param sign  标记索引
     * @param i     交换索引
     */
    private static void exchanger(int[] array, int sign, int i) {
        int temp = array[i];
        array[i] = array[sign];
        array[sign] = temp;
    }


}
